package com.lhcai.lc.other;


import java.util.Arrays;

/**
 * @author lhcstart
 * @create 2023-02-25 22:56
 */

/**
 * 动态规划解答
 */
public class lc322_1 {
    public int coinChange(int[] coins, int amount) {

        if (coins.length == 0) {
            return -1;
        }

        if (amount == 0) {
            return 0;
        }
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1);//不可能达到的数填充数组
        dp[0] = 0;

        for (int i = 1; i < amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    // memo[i]有两种实现的方式，
                    // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
                    // 另一种就是不包含，要兑换的硬币数是memo[i]
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        return dp[amount] ==(amount + 1) ? -1 : dp[amount];
    }

}
